home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 5 / Apprentice-Release5.iso / Source Code / C / Applications / BYacc-CW 1.9 / warshall.c < prev    next >
C/C++ Source or Header  |  1995-05-20  |  1KB  |  79 lines
  1. #include "defs.h"
  2.  
  3. static void transitive_closure(unsigned *R, int n)
  4. {
  5.     register int rowsize;
  6.     register unsigned i;
  7.     register unsigned *rowj;
  8.     register unsigned *rp;
  9.     register unsigned *rend;
  10.     register unsigned *ccol;
  11.     register unsigned *relend;
  12.     register unsigned *cword;
  13.     register unsigned *rowi;
  14.  
  15.     rowsize = WORDSIZE(n);
  16.     relend = R + n*rowsize;
  17.  
  18.     cword = R;
  19.     i = 0;
  20.     rowi = R;
  21.     while (rowi < relend)
  22.     {
  23.     ccol = cword;
  24.     rowj = R;
  25.  
  26.     while (rowj < relend)
  27.     {
  28.         if (*ccol & (1 << i))
  29.         {
  30.         rp = rowi;
  31.         rend = rowj + rowsize;
  32.         while (rowj < rend)
  33.             *rowj++ |= *rp++;
  34.         }
  35.         else
  36.         {
  37.         rowj += rowsize;
  38.         }
  39.  
  40.         ccol += rowsize;
  41.     }
  42.  
  43.     if (++i >= BITS_PER_WORD)
  44.     {
  45.         i = 0;
  46.         cword++;
  47.     }
  48.  
  49.     rowi += rowsize;
  50.     }
  51. }
  52.  
  53. void reflexive_transitive_closure(unsigned *R, int n)
  54. {
  55.     register int rowsize;
  56.     register unsigned i;
  57.     register unsigned *rp;
  58.     register unsigned *relend;
  59.  
  60.     transitive_closure(R, n);
  61.  
  62.     rowsize = WORDSIZE(n);
  63.     relend = R + n*rowsize;
  64.  
  65.     i = 0;
  66.     rp = R;
  67.     while (rp < relend)
  68.     {
  69.     *rp |= (1 << i);
  70.     if (++i >= BITS_PER_WORD)
  71.     {
  72.         i = 0;
  73.         rp++;
  74.     }
  75.  
  76.     rp += rowsize;
  77.     }
  78. }
  79.